package try01;
import java.util.*;

public class MergeIntervals {
	public void tester() {
		List <Interval> a = new ArrayList <Interval> ();
		a.add(new Interval(2,3));
		a.add(new Interval(4,5));
		a.add(new Interval(6,7));
		a.add(new Interval(8,9));
		a.add(new Interval(1,10));
		System.out.println(merge(a));
	}
	
    public List<Interval> merge(List<Interval> intervals) {
    	List <Interval> result = new ArrayList <Interval> ();
    	
    	m(intervals, result);
    
		return result;
    }
    
    public void m(List<Interval> src, List<Interval> dest) {
        while(src.size() != 0) {
        	Interval i = src.get(0);
            src.remove(0);
            
            if(dest.size() == 0) {
            	dest.add(i);
            	continue;
            }
            
            int c = i.start;
            int d = i.end;
            int a, b;
            
            for(int k = 0 ; k <= dest.size();k ++) {
            	if(k == dest.size()) {
            		dest.add(new Interval(c,d));
            		break;
            	}
            	
            	a = dest.get(k).start;
            	b = dest.get(k).end;
            	
            	if(d < a) {
            		dest.add(k, new Interval(c,d));
            		break;
            	}
            	else if(c < a && a<=d && d < b) {
            		dest.set(k, new Interval(c,b));
            		break;
            	}
            	else if(a <= c && d <= b) {
            		break;
            	}
            	else if(c <= a && b <= d) {
            		dest.remove(k);
            		src.add(new Interval(c,d));
            		break;
            	}
            	else if(c <= b) {
            		dest.remove(k);
            		src.add(new Interval(a,d));
            		break;
            	}
            }
        }
    }
    
    // merge a to b
    public void m2(List<Interval> src, List<Interval> dest) {
        if(src.size() == 0) return;
        
        Interval i = src.get(0);
        src.remove(0);
        
        if(dest.size() == 0) {
        	dest.add(i);
        	m(src, dest);
        	return;
        }
        
        int c = i.start;
        int d = i.end;
        int a, b;
        
        for(int k = 0 ; k < dest.size();k ++) {
        	a = dest.get(k).start;
        	b = dest.get(k).end;
        	
        	if(d < a) {
        		dest.add(k, new Interval(c,d));
        		m(src, dest);
        		return;
        	}
        	else if(c < a && a<=d && d < b) {
        		dest.set(k, new Interval(c,b));
        		m(src, dest);
        		return;
        	}
        	else if(a <= c && d <= b) {
        		m(src, dest);
        		return;
        	}
        	else if(c <= a && b <= d) {
        		dest.set(k, new Interval(c,d));
        		m(src, dest);
        		return;
        	}
        	else if(c <= b) {
        		dest.remove(k);
        		src.add(new Interval(a,d));
        		m(src, dest);
        		return;
        	}
        }
        
        dest.add(new Interval(c,d));
        m(src, dest);
        return;
    }
}

class Interval {
	int start;
	int end;
	Interval(){
		this.start = 0;
		this.end = 0;
	}
	Interval(int s, int e) {
		this.start = s;
		this.end = e;
	}
	public String toString() {
		return "["+start+","+end+"]";
	}
}